package src.leetcode.hot.hard_0076;

import java.util.HashMap;
import java.util.Map;

public class minWindow {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minWindow("ADOBECODEBANC", "ABC"));
    }
}


class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> mapori = new HashMap<>();
        Map<Character, Integer> mapcnt = new HashMap<>();
        int numt = t.length(), nums = s.length();

        for (int i = 0; i < numt; i++) {
            mapori.put(t.charAt(i), mapori.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0, right = 0;
        int num = 0;
        int[] index = new int[2];
        index[0] = -1; index[1] = nums;
        while (right <= nums) {
            if (num != numt && right == nums) break;

            if (num != numt) {
                if (mapori.containsKey(s.charAt(right))) {
                    mapcnt.put(s.charAt(right), mapcnt.getOrDefault(s.charAt(right), 0) + 1);
                    if (mapcnt.get(s.charAt(right)) <= mapori.get(s.charAt(right))) {
                        num++;
                    }
                }

                right++;
            } else {
                if (index[1] - index[0] > right - left) {
                    index[0] = left;
                    index[1] = right;
                }
                if (mapcnt.containsKey(s.charAt(left))) {
                    mapcnt.put(s.charAt(left), mapcnt.getOrDefault(s.charAt(left), 0) - 1);
                    if (mapcnt.get(s.charAt(left)) < mapori.get(s.charAt(left))) {
                        num--;
                    }
                }
                left++;
            }
        }

        return (index[1] - index[0]) <= nums ? s.substring(index[0], index[1]) : "";
    }
}